package com.godaiyu.lagou.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author godai
 * @date 2021/8/2 23:18
 * @description
 */
public class GoldMining {

    public static void main(String[] args) {
        List<List<Integer>> goldMine = new ArrayList<>();
        goldMine.add(Arrays.asList(10, 800));
        goldMine.add(Arrays.asList(20, 1800));
        goldMine.add(Arrays.asList(30, 2800));
        goldMine.add(Arrays.asList(40, 3800));
        goldMine.add(Arrays.asList(90, 9800));

        System.out.println(GoldMining.maxGold(goldMine, goldMine.size() - 1, 100));

        System.out.println(GoldMining.maxGold(
                new int[]{10, 20, 30, 40, 90},
                new int[]{800, 1800, 2800, 3800, 9800},
                100)
        );

        System.out.println(GoldMining.maxGold(
                new int[]{10, 20, 30, 20, 91},
                new int[]{800, 1800, 2800, 3800, 9800},
                100)
        );

        System.out.println(GoldMining.maxGold(
                new int[]{10, 20, 30, 40, 190},
                new int[]{800, 1800, 2800, 3800, 9800},
                100)
        );
    }

    public static long maxGold(List<List<Integer>> goldMine, int size, int allResource) {
        if (goldMine == null || size < 0) {
            return 0;
        }

        long max = maxGold(goldMine, size - 1, allResource);
        if (goldMine.get(size).get(0) <= allResource) {
            long tmp = goldMine.get(size).get(1)
                    + maxGold(goldMine, size - 1, allResource - goldMine.get(size).get(0));

            if (tmp > max) {
                max = tmp;
            }
        }
        return max;
    }

    public static long maxGold(int[] need, int[] gold, int maxSize) {
        if (need == null || need.length == 0) {
            return 0;
        }
        if (gold == null || gold.length == 0) {
            return 0;
        }

        if (gold.length != need.length) {
            return 0;
        }

        int[][] dp = new int[need.length + 1][maxSize + 1];

        for (int i = 1; i <= need.length; i++) {
            for (int j = 1; j <= maxSize; j++) {
                if (need[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                    int preMax = gold[i - 1] + dp[i - 1][j - need[i - 1]];
                    if (preMax > dp[i][j]) {
                        dp[i][j] = preMax;
                    }
                }
            }
        }

        return dp[need.length][maxSize];
    }
}
